package com.hr.剑指offer.work1;

import java.util.HashMap;

/**
 * @author 周恒哲
 * @date 2020/06/17
 * 思路：
 * 1.创建HashMap
 * 2.复制结点值
 * 3.复制指向（next,random）
 **/
public class 面试题35_复杂链表的复制 {//HashMap实现

    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap();////创建HashMap集合
        Node cur = head;
        //复制结点值
        while (cur != null) {
            //存储put:<key,value1>
            map.put(cur, new Node(cur.val));//顺序遍历，存储老结点和新结点(先存储新创建的结点值)
            cur = cur.next;
        }
        //复制结点指向
        cur = head;
        while (cur != null) {
            //得到get:<key>.value2,3
            map.get(cur).next = map.get(cur.next);//新结点next指向同旧结点的next指向
            map.get(cur).random = map.get(cur.random); //新结点random指向同旧结点的random指向
            cur = cur.next;
        }
        //返回复制的链表
        return map.get(head);
    }
}
